Depth First and Breadth First Search - Page 2

In the previous page, you received a brief introduction to searching and how our search tree will be defined. In this page, I demonstrate how Depth First Search works.

Depth First Search
Depth first search works by taking a node, checking its neighbors, expanding the first node it finds among the neighbors, checking if that expanded node is our destination, and if not, continue exploring more nodes.

The above explanation is probably confusing if this is your first exposure to depth first search. I hope the following demonstration will help more. Using our same search tree, let's find a path between nodes A and F:

Step 0
Let's start with our root/goal node:

I will be using two lists to keep track of what we are doing - an Open list and a Closed List. An Open list keeps track of what you need to do, and the Closed List keeps track of what you have already done. Right now, we only have our starting point, node A. We haven't done anything to it yet, so let's add it to our Open list.

• Open List: A

• Closed List: <empty>

Step 1
Now, let's explore the neighbors of our A node. To put another way, let's take the first item from our Open list and explore its neighbors:

Node A's neighbors are the B and C nodes. Because we are now done with our A node, we can remove it from our Open list and add it to our Closed List. You aren't done with this step though. You now have two new nodes B and C that need exploring. Add those two nodes to our Open list.

Our current Open and Closed Lists contain the following data:

• Open List: B, C

• Closed List: A

Step 2
Our Open list contains two items. For depth first search and breadth first search, you always explore explore the first item from our Open list. The first item in our Open list is the B node. B is not our destination, so let's explore its neighbors:

Because I have now expanded B, I am going to remove it from the Open list and add it to the Closed List. Our new nodes are D and E, and we add these nodes to the beginning of our Open list:

• Open List: D, E, C

• Closed List: A, B

Step 3
You should start to see a pattern forming. Because D is at the beginning of our Open List, we expand it. D isn't our destination, and it does not contain any neighbors. All you do in this step is remove D from our Open List and add it to our Closed List:

• Open List: E, C

• Closed List: A, B, D

Step 4
We now expand the E node from our Open list. E is not our destination, so we explore its neighbors and find out that it contains the neighbors F and G. Remember, F is our target, but we don't stop here though. Despite F being on our path, we only end when we are about to expand our target Node - F in this case:

Our Open list will have the E node removed and the F and G nodes added. The removed E node will be added to our Closed List:

• Open List: F, G, C

• Closed List: A, B, D, E

Step 5
We now expand the F node. Since it is our intended destination, we stop:

We remove F from our Open list and add it to our Closed List. Since we are at our destination, there is no need to expand F in order to find its neighbors. Our final Open and Closed Lists contain the following data:

• Open List: G, C

• Closed List: A, B, D, E, F

The final path taken by our depth first search method is what the final value of our Closed List is: A, B, D, E, F. Towards the end of this tutorial, I will analyze these results in greater detail so that you have a better understanding of this search method.

On the next page, let's learn how breadth first search would work.

Onwards to the next page!

1 | 2 | 3 | 4 | 5 | 6 | 7